\section{Introduction}
\label{sec-introduction}

The \commonlisp{} standard \cite{ansi:common:lisp} contains very
little information about method combinations.  The dictionary entry in
the standard for the system class \texttt{method-combination} requires
a \emph{method combination object} to be an \emph{indirect instance}
of the system class named \texttt{method-combination}.  The standard
further requires such an object to contain information both about the
\emph{type} of method combination and the \emph{arguments} used with
that type.

The term \emph{indirect instance}, as explained in the glossary,
excludes the possibility of such a method combination object to be an
immediate instance of the class \texttt{method-combination}.  We can
interpret this requirement as the need to create a subclass, say,
\texttt{standard-method-combination} to parallel the situation for
\texttt{method} vs \texttt{standard-method} and
\texttt{generic-function} vs \texttt{standard-generic-function}, i.e.,
so as to allow the programmer to create very different objects from
those that the \texttt{standard-} version can provide.

Clearly, the text of the dictionary entry means that when the macro
\texttt{defgeneric} is used with the \texttt{:method-combination}
option given, such a method combination object is what the generic
function will contain.  We can confirm this view by examining the
description of the MOP generic function
\texttt{generic-function-method-combination} (as described in
\cite{Kiczales:1991:AMP:574212}) which states that the return value is
``a method combination metaobject''.

However, the macro \texttt{define-method-combination} does \emph{not}
define a method combination object.  The reason is of course that no
method-combination options are supplied to this macro.  The dictionary
entry for this macro also clearly says that the macro is used to
define new \emph{types} of method combinations.

The main issue for the person implementing a \commonlisp{} system,
then, is how to interpret the relation between a \emph{method
  combination type} and a \emph{method combination object}.

It is easy to draw the conclusion that a call to the macro
\texttt{define-method-combination} creates a new \emph{class}, as
suggested by the use of the word \emph{type} in the standard, and that
method combination objects of that type are instances of the new
class.  However, this view creates several problems.  In particular,
one must then determine whether each use of the same combination of
the type and the arguments in the \texttt{:method-combination} option
to \texttt{defgeneric} creates a new instance of the class, or whether
existing instances are somehow kept track of and reused.  The first
possibility would have the unfortunate consequence that two calls to
\texttt{generic-function-method-combination} with different
generic-function metaobjects would return two method combination
objects that are not identical.

In this paper, we argue that a \emph{method combination type} is
itself an instance of a completely different class that we shall call
\texttt{method-combination-template}, and that a \emph{method
  combination object} is a \emph{variant} of the template in that it
contains a reference to the template as well as the values of the
\emph{options} that this particular method combination type allows.
To conform to the standard, we obviously maintain that method
combination objects are instances of
\texttt{standard-method-combination}.  This idea is illustrated in
\refFig{fig-method-combinations}, which shows two method combination
templates (\texttt{standard} and \texttt{and}) and two variants of the
\texttt{and} method-combination template; one variant with the option
\texttt{:most-specific-first} and another variant with the option
\texttt{:most-specific-last}.

\begin{figure}
\begin{center}
\inputfig{fig-method-combinations.pdf_t}
\end{center}
\caption{\label{fig-method-combinations}
Representation of method combinations.}
\end{figure}

A call to the macro \texttt{define-method-combination} results in a
function that can be applied to a list of arguments which include at
least a generic function and a list of applicable methods.  This
function becomes associated with the \emph{name} of the
method-combination \emph{type} thus defined.  The standard briefly
uses the term \emph{procedure} to refer to this resulting function.
We adopt that convention in this paper, and refer to the resulting
function as the \emph{method-combination procedure}.

When a generic function is defined or redefined, it would be desirable
to have the options of the \texttt{:method-combination}
\texttt{defgeneric} option checked for validity immediately when the
definition or redefinition occurs.  For the built-in method
combination types, most implementations also handle this check as a
special case.  However, all implementations we have investigated fail
to check the options to a user-defined method-combination type defined
by the long form of the macro \texttt{define-method-combination}.
Instead, if the options are incompatible with the defined
method-combination type, in the best case, an error is signaled when
the method-combination procedure is applied to a list of applicable
methods by the generic function \texttt{compute-effective-method}.
Furthermore, the error being signaled can be hard to decipher, as it
typically results from invalid arguments to a function with a
particular lambda list.

In this paper, we propose a general mechanism for early detection of
incompatible options to a particular method-combination type.  This
mechanism is available to the creator of custom method-combination
types, and also used to verify the options to the built-in
method-combination types.

The macro \texttt{define-method-combination} comes in two versions
called the \emph{long form} and the \emph{short form} in the
\commonlisp{} standard.  The short form of the macro can be expressed
in terms of the long form, but it may not be obvious how the options
to the short form should be propagated to the long form.

Furthermore, in the description of the short form of the macro, the
standard states that the method-combination procedure resulting from
such a definition accepts an optional argument (named \texttt{order})
that can have two values, \texttt{:most-specific-first} and
\texttt{:most-specific-last}, with the value
\texttt{:most-specific-first} being the default.  It is not obvious
how this restriction can be expressed as a long-form definition of a
similar procedure.  A common solution to this problem is to define a
subclass \texttt{short-method-combination} of the class
\texttt{method-combination}, and to introduce special-purpose code for
checking this restriction.  The technique presented in this paper does
not require such a subclass, as the long-form version of the
short-form definition is able to check the restriction.

Throughout this paper, we assume that it is an error to attempt to
create a generic function using a method-combination type that is not
already created.  Recall that the standard states that when a
\texttt{define-method-combination} form appears at the top level, the
compiler must recognize the name of that type as valid in subsequent
\texttt{defgeneric} forms, but that the resulting method-combination
procedure is not executed until the \texttt{define-method-combination}
form itself is executed.  In other words, since the method-combination
type is not created at compile time, it may not exist when a
\texttt{defgeneric} form using the name is encountered by the
compiler.  However, our assumption is still valid, since the compiler
also does not create the generic function when a \texttt{defgeneric}
form appears at the top level.

For example, assume that some source file contains a
\texttt{define-method-combination} form, defining a method combination
type with a new name, followed by a \texttt{defgeneric} form that
refers to that method combination type in the
\texttt{:method-combination} option of the \texttt{:defgeneric} form.
When the compiler encounters the \texttt{define-method-combination}
form, it registers its name as being valid for use in subsequent
\texttt{defgeneric} forms, but the compiler does not \emph{create} the
method-combination type.  Subsequently, when the compiler encounters
the \texttt{defgeneric} form, it recognizes a valid name of a
method-combination type, but since the compiler also does not create
the generic function when the \texttt{defgeneric} form is encountered,
there is no need for the method-combination type to have been created.
When the compiled file is later loaded, the new method-combination
type is first created.  Subsequently, the generic function is created,
referring to an existing method-combination type.  In this paper, we
do not address the mechanism by which the compile-time behavior
required by the standard is implemented.

There are several scenarios that are discussed in this paper:

\begin{enumerate}
\item The user correctly defines a custom method-combination type
  using \texttt{define-method-combination}.  Subsequently, the user
  defines a generic function with that method-combination type, but
  makes a mistake in the list of options.
\item The user defines a custom method-combination type using the long
  form of \texttt{define-method-combination}, but makes a mistake in
  the lambda list supplied to the macro, so that the options of the
  resulting method-combination procedure are not the ones that were
  intended.  Subsequently, the user defines a generic function with a
  list of options that were intended to be acceptable.
\item The user initially correctly defines a custom method combination
  type using \texttt{define-method-combination}, and then also
  correctly defines one or more generic functions with that method
  combination type.  Then the user decides to make a change to the
  code of the method-combination type, so the
  \texttt{define-method\-combination} form is re-executed, but the new
  lambda list is incompatible with the options given when the generic
  functions were created, either as a result of a mistake or of a
  deliberate decision.
\end{enumerate}

\noindent
To illustrate these scenarios, we can imagine a restricted form of the
\texttt{and} method combination that does not admit any
\texttt{:around} methods.  This restriction means that the short form
of \texttt{define-method-combination} can not be used.

An example of the first scenario would be the following code:

{\small\begin{verbatim}
(define-method-combination simple-and
    (&optional (order :most-specific-first))
    (primary (and) :order order :required t)
 ...)

(defgeneric simple-and (...)
  (:method-combination simple-and :msot-specific-first))
\end{verbatim}}

\noindent
Here, the user has a typo in the second form.
An example of the second scenario would be the following code:

{\small\begin{verbatim}
(define-method-combination simple-and
    (&optional (order :msot-specific-first))
    (primary (and) :order order :required t)
 ...)

(defgeneric simple-and (...)
  (:method-combination simple-and :most-specific-first))
\end{verbatim}}

\noindent
Here, the user has a typo in the first form.
Finally, an example of the third form would be the following code:

{\small\begin{verbatim}
(define-method-combination simple-and
    (&optional (order :most-specific-first))
    (primary (and) :order order :required t)
 ...)

(defgeneric simple-and (...)
  (:method-combination simple-and :most-specific-first))
\end{verbatim}}

\noindent
Here, there are no mistakes, but the user later decides to disallow
the option , so the first form is altered to become:

{\small\begin{verbatim}
(define-method-combination simple-and ()
    (primary (and) :order :most-specific-first
                   :required t)
 ...)
\end{verbatim}}

\noindent
In the first two scenarios, the ideal consequence would be that a
warning is initially signaled, stating that the options supplied to
the creation of the generic function are incompatible with the type of
the desired method combination.  Any subsequent attempt to execute the
generic function would result in an appropriate error being signaled.
Once the incorrect definition has been corrected and the corresponding
form has been re-executed, the generic function should be operational.

In the third scenario, the ideal consequence would be that a warning
is signaled, giving a list of generic functions with a list of options
that are now incompatible with the redefined method-combination type.
Any subsequent attempt to execute one of these generic functions would
result in an appropriate error being signaled.  If a mistake was made,
the re-execution of a corrected \texttt{define-method-combination}
form should render the existing generic functions operational again.
If the change was deliberate, the list of generic functions in the
message can be used to determine which definitions to correct and
re-execute.

The technique described in this paper handles all these scenarios, but
it has been implemented only partially.  We are currently working on
incorporating the remaining elements of our technique into the
\sicl{}%
\footnote{https://github.com/robert-strandh/SICL}
code base.
